package com.njupt.HuiSu;

import java.util.ArrayList;
import java.util.List;

public class SolveNQueens {
    public int[] location;
    public int n;

    public SolveNQueens(int n) {
        this.location = new int[n];
        this.n = n;
    }



    public boolean isLocation(int k,int i,int[] location){
        for (int j = 0; j < k; j++) {
            if(location[j]==i || Math.abs(location[j]-i) == Math.abs(k-j)){
                return false;
            }
        }
        return true;
    }

    public void nQueens(int k,int n,int[] location){
        //遍历每一行n个棋盘格子
        for (int i = 0; i <n ; i++) {
            //第k个皇后能够放入第i个棋盘格子
            if(isLocation(k,i,location)){
                location[k] = i;
                if(k == n-1){
                    for (int j = 0; j < location.length; j++) {
                        System.out.print(location[j]+ " ");
                    }
                    System.out.println();
                }else {
                    nQueens(k+1,n,location);
                }
            }
        }
    }


    public static void main(String[] args) {
        SolveNQueens test = new SolveNQueens(4);
       test.nQueens(0, test.n, test.location);

    }
}
